package week02

// 105. 从前序与中序遍历序列构造二叉树
// https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

// 从前序遍历可以知道根节点
// 从中序遍历可以知道左右子树节点数量

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 {
		return nil
	}

	var node = &TreeNode{}
	node.Val = preorder[0]
	// 从中序遍历中找到根节点位置，得到左右子树节点数量
	var rootIndex = 0
	for i, val := range inorder {
		if val == node.Val {
			rootIndex = i
			break
		}
	}

	// 注意：当前点(node.Val)不在任何一个子树中

	// 左半部分是左子树节点，构建左子树
	node.Left = buildTree(preorder[1:rootIndex+1], inorder[:rootIndex])
	// 右半部分是右子树节点，构建右子树
	node.Right = buildTree(preorder[rootIndex+1:], inorder[rootIndex+1:])
	return node
}

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}